// 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

const maxProfit = function (prices: number[]): number {
    if (prices.length < 2) {
        return 0;
    }
    // 初始状态dp数组
    // dp[1]表示现在持有股票，dp[0]表示现在没有持有股票
    const dp: number[][] = [
        [0],
        [-prices[0]],
    ];
    // 状态转移方程
    for (let i = 1; i < prices.length; i++) {
        dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1] + prices[i]);
        dp[1][i] = Math.max(dp[1][i - 1], dp[0][i - 1] - prices[i])
    }
    return dp[0][prices.length - 1];
};


// 这道题目是一道典型的动态规划的题目
// 如果没有一个确切的方法论，空想起来确实会十分困难
// 首先我们定义状态，这里需要有两维的dp数组
// ！！动态规划的关键在于只考虑最近邻的两个状态！！
// 一维：表示当前开盘前是否持有股票，它会影响我们在当天可以进行的行为；
// 0表示未持有，1表示持有
// 二维：表示当天情况下的最大利润，需要由之前的状态推导得来
// 我们分情况讨论：
// 在持有股票时，我们当天只能存在两个操作
// 操作一：什么都不做等待一天，这个情况下不需要做状态转移，保存上一天的状态即可
// 操作二：持有股票时可以卖出，卖出的情况是我们假定昨天（可以买入股票时拥有的最大利润）买入今天卖出
// 我们比较这两个操作可以得出持有股票时今天的最大利润
// 在开盘前没有股票时，我们当天只能存在两个操作
// 操作一：同上，什么都不做等待一天，这个情况下不需要做状态转移
// 操作二：买入股票，这个情况下我们需要假定昨天（持有股票时已经拥有的最大利润）减去购入股票的价格
// 同样比较这两个操作得到最大利润
// 我们再初始化状态为[0,-prices[0]（因为第一天买入是亏钱的）]
// 通过上述逻辑，推导出dp数组后，返回最后一天未持有股票（抛出肯定比没抛赚钱）时的状态即可得到结果。